package com.lazycat.leetcode.editor.cn;
//2023-04-09 15:11:38
//给你一个正整数数组 nums 。 
//
// 同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任
//意 次： 
//
// 
// 将数组里一个元素 增大 或者 减小 1 。 
// 
//
// 请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。 
//
// 注意，每次查询后，数组变回最开始的值。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [3,1,6,8], queries = [1,5]
//输出：[14,10]
//解释：第一个查询，我们可以执行以下操作：
//- 将 nums[0] 减小 2 次，nums = [1,1,6,8] 。
//- 将 nums[2] 减小 5 次，nums = [1,1,1,8] 。
//- 将 nums[3] 减小 7 次，nums = [1,1,1,1] 。
//第一个查询的总操作次数为 2 + 5 + 7 = 14 。
//第二个查询，我们可以执行以下操作：
//- 将 nums[0] 增大 2 次，nums = [5,1,6,8] 。
//- 将 nums[1] 增大 4 次，nums = [5,5,6,8] 。
//- 将 nums[2] 减小 1 次，nums = [5,5,5,8] 。
//- 将 nums[3] 减小 3 次，nums = [5,5,5,5] 。
//第二个查询的总操作次数为 2 + 4 + 1 + 3 = 10 。
// 
//
// 示例 2： 
//
// 输入：nums = [2,9,6,3], queries = [10]
//输出：[20]
//解释：我们可以将数组中所有元素都增大到 10 ，总操作次数为 8 + 1 + 4 + 7 = 20 。
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// m == queries.length 
// 1 <= n, m <= 10⁵ 
// 1 <= nums[i], queries[i] <= 10⁹ 
// 
//
// Related Topics 数组 二分查找 前缀和 排序 👍 16 👎 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class MinimumOperationsToMakeAllArrayElementsEqual {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new MinimumOperationsToMakeAllArrayElementsEqual().new Solution();

        solution.minOperations(new int[]{2,9,6,3},new int[]{10});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Long> minOperations(int[] nums, int[] queries) {

        Arrays.sort(nums);
        int len = nums.length;

        long[] next = new long[len+1];

        for(int i = 0;i<len;i++){
            next[i+1] = next[i] + nums[i];
        }

        List<Long> ans = new ArrayList<>();

        for(int val : queries){
            int j = lowerBound(nums,val);
            long left = (long) val * j - next[j];
            long right = next[len] - next[j] - (long) val*(len-j);
            ans.add(left + right);
        }
        return ans;
    }

    private int lowerBound(int[] nums,int val){
        int left = -1;
        int right = nums.length;

        while (left+1<right){
            int mid = (left+right)/2;
            if(nums[mid] < val){
                left = mid;
            }else{
                right = mid;
            }
        }
        return right;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}